# 给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
#
#  示例 1:
#
#  输入: [5,7]
# 输出: 4
#
#  示例 2:
#
#  输入: [0,1]
# 输出: 0
#  Related Topics 位运算
#  👍 172 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def rangeBitwiseAnd(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        # 寻找最长公共前缀
        # 比如从5（101）到7（111），一共5、6、7三个数字，6
        # 是（110）为什么按位与的结果是4（100）？
        # 是因为公共前缀是最高位的1，之后的每一位部分必定是有0出现，那么按照“只有1和1与为1”的原则，结果就是100



        #
        move = 0
        while m < n:
            m >>= 1
            n >>= 1
        return m << move
        # leetcode submit region end(Prohibit modification and deletion)
